{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct K Palindrome Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #hash-table #string #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #哈希表 #字符串 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canConstruct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #构造 K 个回文字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code>&nbsp;和一个整数 <code>k</code>&nbsp;。请你用 <code>s</code>&nbsp;字符串中 <strong>所有字符</strong>&nbsp;构造 <code>k</code>&nbsp;个非空 <strong>回文串</strong>&nbsp;。</p>\n",
    "\n",
    "<p>如果你可以用&nbsp;<code>s</code>&nbsp;中所有字符构造&nbsp;<code>k</code>&nbsp;个回文字符串，那么请你返回 <strong>True</strong>&nbsp;，否则返回&nbsp;<strong>False</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;annabelle&quot;, k = 2\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>可以用 s 中所有字符构造 2 个回文字符串。\n",
    "一些可行的构造方案包括：&quot;anna&quot; + &quot;elble&quot;，&quot;anbna&quot; + &quot;elle&quot;，&quot;anellena&quot; + &quot;b&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;leetcode&quot;, k = 3\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>无法用 s 中所有字符构造 3 个回文串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;true&quot;, k = 4\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>唯一可行的方案是让 s 中每个字符单独构成一个字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;yzyzyzyzyzyzyzy&quot;, k = 2\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>你只需要将所有的 z 放在一个字符串中，所有的 y 放在另一个字符串中。那么两个字符串都是回文串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;cr&quot;, k = 7\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>我们没有足够的字符去构造 7 个回文串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10^5</code></li>\n",
    "\t<li><code>s</code>&nbsp;中所有字符都是小写英文字母。</li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10^5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-k-palindrome-strings](https://leetcode.cn/problems/construct-k-palindrome-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-k-palindrome-strings](https://leetcode.cn/problems/construct-k-palindrome-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"annabelle\"\\n2', '\"leetcode\"\\n3', '\"true\"\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        cnt = Counter(s)\n",
    "        count = sum(1 for _, value in cnt.items() if value % 2 == 1)\n",
    "        left = max(count, 1)\n",
    "        return left <= k <= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        # 右边界为字符串的长度\n",
    "        right = len(s)\n",
    "        # 统计每个字符出现的次数\n",
    "        occ = collections.Counter(s)\n",
    "        # 左边界为出现奇数次字符的个数\n",
    "        left = sum(1 for _, v in occ.items() if v % 2 == 1)\n",
    "        # 注意没有出现奇数次的字符的特殊情况\n",
    "        left = max(left, 1)\n",
    "        return left <= k <= right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        # 统计所有字符的出现次数\n",
    "        counterS = Counter(s)\n",
    "        # 最多可支持的k的数量\n",
    "        right = len(s)\n",
    "        # 要找到其最少可支持的数量\n",
    "        # 每当有一个大于1次的 numberCounter的左侧就能少一种，因为他可以\n",
    "        left = sum(map(lambda values:values[1]%2,counterS.items()))\n",
    "        return left<=k<=right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        return sum(i & 1 for i in Counter(s).values()) <= k and len(s) >= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        if len(s)<k:\n",
    "            return False;\n",
    "        c = Counter(s)\n",
    "        total = sum([1 for e,x in c.items() if x%2==1])\n",
    "        return total<=k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        return True if len(s)>=k>=len([v for v in Counter(s).values() if v % 2 == 1]) else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        ans = 0\n",
    "        for v in Counter(s).values():\n",
    "            if v % 2 == 1:\n",
    "                ans += 1\n",
    "        if len(s)>=k>=ans:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        max_count = len(s)\n",
    "        from collections import Counter\n",
    "        count_each_char = Counter(s)\n",
    "        min_count = 0\n",
    "        for _, count in count_each_char.items():\n",
    "            if count % 2 == 1:\n",
    "                min_count += 1\n",
    "        min_count = max(min_count, 1)\n",
    "        return min_count <= k <= max_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    # Greedy. Time O(n) Space O(1)\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        cnt = Counter(s)\n",
    "        minPairs, maxPairs = 0, 0\n",
    "        for key, val in cnt.items():\n",
    "            if val % 2 != 0:\n",
    "                minPairs += 1\n",
    "            maxPairs += val\n",
    "        minPairs = max(1, minPairs)\n",
    "        return minPairs <= k and maxPairs >= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        if len(s)<k:\n",
    "            return False;\n",
    "        c = Counter(s)\n",
    "        total = sum(v%2 for v in c.values())\n",
    "        return total<=k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        c = Counter(s)\n",
    "        # 奇数的数量小于等于k，并且总长大于等于k即可\n",
    "        return sum(i & 1 for i in c.values()) <= k and len(s) >= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        counter = Counter(s)\n",
    "        odd = sum(1 if v % 2 == 1 else 0 for v in counter.values())\n",
    "        odd = max(odd, 1)\n",
    "        return odd <= k <= n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        if len(s) < k:\n",
    "            return False\n",
    "        char_cnt = Counter(s)\n",
    "\n",
    "        cnt = 0\n",
    "\n",
    "        for key, value in char_cnt.items():\n",
    "            if value % 2 != 0:\n",
    "                cnt += 1\n",
    "        return cnt <= k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s, k):\n",
    "        #注意到某个字符出现偶数次，是可以任意添加到某个回文串中不影响的\n",
    "        #奇数次的字符，就必定会占一个中间位\n",
    "        if k == len(s):\n",
    "            return True\n",
    "        if k > len(s):\n",
    "            return False\n",
    "        cnt =[x % 2 for x in collections.Counter(s).values()] \n",
    "        singularCnt = sum(cnt)        \n",
    "        if singularCnt <= k:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s, k):\n",
    "        #注意到某个字符出现偶数次，是可以任意添加到某个回文串中不影响的\n",
    "        #奇数次的字符，就必定会占一个中间位\n",
    "        if k == len(s):\n",
    "            return True\n",
    "        if k > len(s):\n",
    "            return False\n",
    "        cnt = {}\n",
    "        for char in s:\n",
    "            cnt[char] = (cnt.get(char, 0) + 1) % 2\n",
    "        singularCnt = sum(cnt.values())        \n",
    "        if singularCnt <= k:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        # 注意审题 字符可以用任意顺序排序\n",
    "        right = len(s)\n",
    "        occ = collections.Counter(s)\n",
    "        left = sum(1 for _, v in occ.items() if v % 2 == 1)\n",
    "        left = max(1, left)\n",
    "        return left <= k <= right\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        if len(s) < k:\n",
    "            return False\n",
    "\n",
    "        hashmap = {}\n",
    "        for i in s:\n",
    "            hashmap[i] = hashmap.get(i, 0) + 1\n",
    "        n = 0\n",
    "        for v in hashmap.values():\n",
    "            if v & 1:\n",
    "                k -= 1\n",
    "        return k >= 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        a = Counter(s)\n",
    "        t = 0\n",
    "        for i in a.values():\n",
    "            if i%2==1:\n",
    "                t+=1\n",
    "            if t>k or  k>len(s):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        n = len(s)\n",
    "        return n >= k and sum(map(lambda x: x % 2, Counter(s).values())) <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        cnt = Counter(s)\n",
    "        ans = 0 \n",
    "        if k>len(s):\n",
    "            return False\n",
    "        for c in cnt:\n",
    "            cnt[c] = cnt[c]%2\n",
    "            if cnt[c]==1:  ans += 1 \n",
    "        return k>=ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        return len(s) >= k and sum(i & 1 for i in Counter(s).values()) <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        # 因为小的回文串可以从大的回文串里面分裂出来，\n",
    "        # 或者说短的回文串可以全部拼起来成为最长的回文串\n",
    "        # 计算出最长的回文串，确定最少的回文串数量\n",
    "        # 而最多的回文串数量就是字符串的长度n，即全部单个字符作为回文串\n",
    "        n = len(s)\n",
    "        cnt = Counter(s)\n",
    "        single_num = 0\n",
    "        for _,v in cnt.items():\n",
    "            single_num += (v - (v // 2)*2)\n",
    "        if single_num<=k<=n:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        # 右边界为字符串的长度\n",
    "        right = len(s)\n",
    "        # 统计每个字符出现的次数\n",
    "        occ = collections.Counter(s)\n",
    "        # 左边界为出现奇数次字符的个数\n",
    "        left = sum(1 for _, v in occ.items() if v % 2 == 1)\n",
    "        # 注意没有出现奇数次的字符的特殊情况\n",
    "        left = max(left, 1)\n",
    "        return left <= k <= right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        return sum(1 for k, v in Counter(s).items() if v % 2) <= k <= len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        if len(s) < k:\n",
    "            return False\n",
    "\n",
    "        count = set()\n",
    "        for ch in s:\n",
    "            if ch not in count:\n",
    "                count.add(ch)\n",
    "            else:\n",
    "                count.remove(ch)\n",
    "\n",
    "        return len(count) <= k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        cnt = [0]*26\n",
    "        for letter in s:\n",
    "            cnt[ord(letter)-97] += 1\n",
    "        single_cnt = 0\n",
    "        double_cnt = 0\n",
    "        for i in cnt:\n",
    "            if i != 0:\n",
    "                double_cnt += i//2\n",
    "                if i%2 == 1:\n",
    "                    single_cnt += 1\n",
    "        print(cnt)\n",
    "        print(single_cnt)\n",
    "        print(double_cnt)\n",
    "        if single_cnt > k:\n",
    "            return False\n",
    "        elif double_cnt+single_cnt < k:\n",
    "            tmp = k-single_cnt\n",
    "            if tmp % 2 == 0:\n",
    "                if double_cnt < tmp//2:\n",
    "                    return False\n",
    "                else:\n",
    "                    return True\n",
    "\n",
    "            elif double_cnt < tmp-double_cnt:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s, k):\n",
    "        #注意到某个字符出现偶数次，是可以任意添加到某个回文串中不影响的\n",
    "        #奇数次的字符，就必定会占一个中间位\n",
    "        if k == len(s):\n",
    "            return True\n",
    "        if k > len(s):\n",
    "            return False\n",
    "        cnt = {}\n",
    "        for char in s:\n",
    "            cnt[char] = (cnt.get(char, 0) + 1) % 2\n",
    "        singularCnt = sum(cnt.values())        \n",
    "        if singularCnt <= k:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        cnt = [0]*26\n",
    "        for letter in s:\n",
    "            cnt[ord(letter)-97] += 1\n",
    "        single_cnt = 0\n",
    "        double_cnt = 0\n",
    "        for i in cnt:\n",
    "            if i != 0:\n",
    "                double_cnt += i//2\n",
    "                if i%2 == 1:\n",
    "                    single_cnt += 1\n",
    "        if single_cnt > k:\n",
    "            return False\n",
    "        elif double_cnt+single_cnt < k:\n",
    "            tmp = k-single_cnt\n",
    "            if tmp % 2 == 0:\n",
    "                if double_cnt < tmp//2:\n",
    "                    return False\n",
    "                else:\n",
    "                    return True\n",
    "\n",
    "            elif double_cnt < tmp-double_cnt:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        if len(s)<k:\n",
    "            return False\n",
    "        dic=Counter(s)\n",
    "        j,o=0,0\n",
    "        for c in dic:\n",
    "            if dic[c]%2==1:\n",
    "                j+=1\n",
    "            o+=dic[c]//2\n",
    "\n",
    "        return j<=k<=len(s)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        cnt = [0]*26\n",
    "        for letter in s:\n",
    "            cnt[ord(letter)-97] += 1\n",
    "        single_cnt = 0\n",
    "        double_cnt = 0\n",
    "        for i in cnt:\n",
    "            double_cnt += i//2\n",
    "            if i%2 == 1:\n",
    "                single_cnt += 1\n",
    "        tmp = k-single_cnt\n",
    "        if tmp < 0:\n",
    "            return False\n",
    "        elif double_cnt < tmp:\n",
    "            if  tmp % 2 == 0:\n",
    "                if double_cnt < tmp//2:\n",
    "                    return False\n",
    "                else:\n",
    "                    return True\n",
    "            elif tmp > 2*double_cnt:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s, k):\n",
    "        #注意到某个字符出现偶数次，是可以任意添加到某个回文串中不影响的\n",
    "        #奇数次的字符，就必定会占一个中间位\n",
    "        if k == len(s):\n",
    "            return True\n",
    "        if k > len(s):\n",
    "            return False\n",
    "        cnt = {}\n",
    "        for char in s:\n",
    "            cnt[char] = (cnt.get(char, 0) + 1) % 2\n",
    "        singularCnt = sum(cnt.values())        \n",
    "        if singularCnt <= k:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        return len(s) >= k and sum(i & 1 for i in Counter(s).values()) <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        cnt = [0]*26\n",
    "        for letter in s:\n",
    "            cnt[ord(letter)-97] += 1\n",
    "        single_cnt = 0\n",
    "        double_cnt = 0\n",
    "        for i in cnt:\n",
    "            double_cnt += i//2\n",
    "            if i%2 == 1:\n",
    "                single_cnt += 1\n",
    "        if single_cnt > k:\n",
    "            return False\n",
    "        elif double_cnt+single_cnt < k:\n",
    "            if  k-single_cnt % 2 == 0:\n",
    "                if double_cnt < tmp//2:\n",
    "                    return False\n",
    "                else:\n",
    "                    return True\n",
    "            elif k > 2*double_cnt+single_cnt:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        q=Counter(s)\n",
    "        m=0\n",
    "        c=0\n",
    "        for x in q.items():\n",
    "            if x[1]%2:\n",
    "                c+=1\n",
    "            else:\n",
    "                m+=1\n",
    "        return  c<=k<=len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        right = len(s)\n",
    "        # 统计每个字符出现的次数\n",
    "        occ = collections.Counter(s)\n",
    "        # 左边界为出现奇数次字符的个数\n",
    "        left = sum(1 for _, v in occ.items() if v % 2 == 1)\n",
    "        # 注意没有出现奇数次的字符的特殊情况\n",
    "        left = max(left, 1)\n",
    "        return left <= k <= right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s, k):\n",
    "        #注意到某个字符出现偶数次，是可以任意添加到某个回文串中不影响的\n",
    "        #奇数次的字符，就必定会占一个中间位\n",
    "        if k == len(s):\n",
    "            return True\n",
    "        if k > len(s):\n",
    "            return False\n",
    "        cnt = {}\n",
    "        for char in s:\n",
    "            cnt[char] = (cnt.get(char, 0) + 1) % 2\n",
    "        singularCnt = sum(cnt.values())        \n",
    "        if singularCnt <= k:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        if len(s) < k:\n",
    "            return False\n",
    "        s = Counter(s)\n",
    "        cnt = 0\n",
    "        for v in s.values():\n",
    "            if v % 2 == 1:\n",
    "                cnt += 1\n",
    "        return cnt <= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        cnt = [0]*26\n",
    "        for letter in s:\n",
    "            cnt[ord(letter)-97] += 1\n",
    "        single_cnt = 0\n",
    "        double_cnt = 0\n",
    "        for i in cnt:\n",
    "            double_cnt += i//2\n",
    "            if i%2 == 1:\n",
    "                single_cnt += 1\n",
    "        if single_cnt > k:\n",
    "            return False\n",
    "        elif double_cnt+single_cnt < k:\n",
    "            if  k-single_cnt % 2 == 0:\n",
    "                if double_cnt < tmp//2:\n",
    "                    return False\n",
    "                else:\n",
    "                    return True\n",
    "            elif k > 2*double_cnt+single_cnt:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        dict_=defaultdict(int)\n",
    "\n",
    "        for c in s:\n",
    "            dict_[c]+=1\n",
    "\n",
    "        #print(dict_)\n",
    "\n",
    "        \n",
    "\n",
    "        cnt=0\n",
    "\n",
    "        for key in dict_:\n",
    "            if(dict_[key]%2!=0):\n",
    "                cnt+=1\n",
    "\n",
    "        \n",
    "        if(len(s)<k):\n",
    "            return False\n",
    "\n",
    "        return cnt<=k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s, k):\n",
    "        #注意到某个字符出现偶数次，是可以任意添加到某个回文串中不影响的\n",
    "        #奇数次的字符，就必定会占一个中间位\n",
    "        if k == len(s):\n",
    "            return True\n",
    "        if k > len(s):\n",
    "            return False\n",
    "        cnt = {}\n",
    "        for char in s:\n",
    "            cnt[char] = (cnt.get(char, 0) + 1) % 2\n",
    "        singularCnt = sum(cnt.values())        \n",
    "        if singularCnt <= k:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        if len(s) < k:\n",
    "            return False\n",
    "\n",
    "        hashmap = {}\n",
    "        for i in s:\n",
    "            hashmap[i] = hashmap.get(i, 0) + 1\n",
    "        for v in hashmap.values():\n",
    "            if v & 1:\n",
    "                k -= 1\n",
    "        return k >= 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        return len(s) >= k and sum(map(lambda x: x % 2, Counter(s).values())) <= k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canConstruct(self, s: str, k: int) -> bool:\n",
    "        if len(s) < k:\n",
    "            return False\n",
    "        char_cnt = Counter(s)\n",
    "\n",
    "        cnt = 0\n",
    "\n",
    "        for key, value in char_cnt.items():\n",
    "            if value % 2 != 0:\n",
    "                cnt += 1\n",
    "        return cnt <= k\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
